package com.zrkizzy.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * 142. 环形链表 II
 *
 * @author zhangrongkang
 * @see <a href="https://leetcode.cn/problems/linked-list-cycle-ii/description/">
 * https://leetcode.cn/problems/linked-list-cycle-ii/description/
 * </a>
 * @since 2022/11/17
 */
public class 环形链表II {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    class Solution01 {
        // 哈希表
        public ListNode detectCycle(ListNode head) {
            // 定义用于存储链表节点的哈希表
            Map<ListNode, Integer> map = new HashMap<>();
            // 遍历一次链表
            while (head != null) {
                // 如果哈希表中存在当前节点说明存在环
                if (map.containsKey(head)) {
                    return head;
                }
                map.put(head, 0);
                head = head.next;
            }
            return null;
        }
    }

    class Solution02 {
        // 双指针
        public ListNode detectCycle(ListNode head) {
            // 定义快慢指针
            ListNode slow = head, fast = head;
            // 循环
            while (true) {
                // 如果不存在环形链表，同时确保快指针在移动的过程中不出现null
                if (fast == null || fast.next == null) {
                    return null;
                }
                // 移动快慢指针
                fast = fast.next.next;
                slow = slow.next;
                // 找到第一次重合的位置后跳出循环
                if (fast == slow) {
                    break;
                }
            }
            // 将快指针移动到链表的头部
            fast = head;

            // 第二次重合的位置就是第一个环节点
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }

            return fast;
        }
    }
}
